package com.sourcetrip.my;


import com.sourcetrip.my.abs.AbstractList;

import java.util.Arrays;

/**
 * @author: ZhouBert
 * @date: 2020/12/13
 * @description: 我的动态数组
 * 设计关键：
 * 1.动态扩容：每一次扩容 1.5 倍；
 * 2.动态缩容：当数据小于当前的 1/4 时，进行缩容缩小到原来的 1/2；但是最少为 DEFAULT_CAPACITY
 * --
 * 难点：
 * 1.add():考虑 扩容；
 * 2.remove():考虑 缩容
 * 3.indexOf():比较两个元素，需要考虑 null 的情况
 * --
 * 优化：
 * 1.arr 用 E[] 是没问题的，不知道当初为啥选择用 Object[]
 * 2.
 */
public class ArrayListV0<E> extends AbstractList<E> {

	/**
	 * 默认容量大小
	 */
	private final int DEFAULT_CAPACITY = 10;

	/**
	 * 默认
	 */
	protected Object[] arr = new Object[DEFAULT_CAPACITY];

	/**
	 * 重新给 arr 分配一个内存地址
	 */
	@Override
	public void clear() {
		arr = new Object[DEFAULT_CAPACITY];
		size = 0;
	}

	/**
	 * 根据索引拿到对应的元素
	 *
	 * @param index 索引参数
	 * @return 索引对应的元素
	 */
	@Override
	public E get(int index) {
		rangeCheck(index);
		return (E) arr[index];
	}

	/**
	 * 在对应索引的地方设置元素
	 *
	 * @param index   索引
	 * @param element 元素
	 * @return 旧元素
	 */
	@Override
	public E set(int index, E element) {
		rangeCheck(index);
		E oldValue = (E) arr[index];
		arr[index] = element;
		return oldValue;
	}

	/**
	 * 在 index 的位置添加 element
	 * 优化：让扩容后只搬运一次元素
	 *
	 * @param index   索引
	 * @param element 元素
	 */
	@Override
	public void add(int index, E element) {
		rangeCheckForAdd(index);
		size++;
		Object[] temp = arr;
		try {
			if (size == arr.length) {
				System.out.println("进行了扩容：size " + size);
				//执行扩容
				int newCapacity = size + (size >> 1);
				Object[] arrAfterExpansion = new Object[newCapacity];
				//1.先把 index 之前的数组拷贝进来
				System.arraycopy(arr, 0, arrAfterExpansion, 0, index);
				//2.再执行新 e 的添加
				arrAfterExpansion[index] = element;
				//3.最后再拷贝其他元素到 arrAfterExpansion
				System.arraycopy(arr, index, arrAfterExpansion, index + 1, size - index);
				arr = arrAfterExpansion;

				return;
			}
			//不需要扩容
			//1.先拷贝 index 之后的元素
			System.arraycopy(arr, index, arr, index + 1, size - index);
			//2.再将 index 的元素放进去
			arr[index] = element;
		} catch (Exception e) {
			size--;
		} finally {
			System.out.println("此时数组：" + Arrays.toString(arr));
		}
	}

	/**
	 * 移除 index 下的元素
	 * 考虑缩容
	 *
	 * @param index
	 * @return
	 */
	@Override
	public E remove(int index) {
		rangeCheck(index);
		E oldValue = (E) arr[index];
		size--;
		try {
//当 size > 20 时才有必要进行缩容
			if (size < (arr.length >> 2) && (size > 20)) {
				System.out.println("进行了缩容：size " + size);
				//执行缩容
				int newCapacity = arr.length >> 1;
				Object[] arrAfterShrinkage = new Object[newCapacity];
				//1.拷贝 index 之前的数组
				System.arraycopy(arr, 0, arrAfterShrinkage, 0, index);
				//2.拷贝 index 之后的数组
				System.arraycopy(arr, index + 1, arrAfterShrinkage, index, size - index);
				arr = arrAfterShrinkage;
				return oldValue;
			}
			//不需要缩容
			//1.拷贝 index 之前的数组
			System.arraycopy(arr, index + 1, arr, index, size - index);
			//2.将最后的元素置为null
			arr[size] = null;
		} catch (Exception e) {
			size++;
		} finally {
			System.out.println("此时数组：" + Arrays.toString(arr));
			return oldValue;
		}
	}

	/**
	 * 遍历判断元素
	 *
	 * @param element
	 * @return
	 */
	@Override
	public int indexOf(E element) {
		if (element == null) {
			for (int i = 0; i < size; i++) {
				if (arr[i] == null) {
					return i;
				}
			}
		} else {
			for (int i = 0; i < size; i++) {
				if (element.equals(arr[i])) {
					return i;
				}
			}
		}
		return ELEMENT_NOT_FOUND;
	}

	@Override
	public String toString() {
		return Arrays.toString(arr);
	}


	//private methods

	/**
	 * 添加时扩容判断
	 * 设计之前已经执行了 size++
	 */
	private void ensureCapacityForAdd() {
		if (size == arr.length) {
			//执行扩容
			int newCapacity = size + size >> 1;
			Object[] tempArr = new Object[newCapacity];
			//进行迁移

		}
	}

	//


}
